package com.lw.leetcode.sort.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1606. 找到处理最多请求的服务器
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/30 9:34
 */
public class BusiestServers {

    public static void main(String[] args) {
        BusiestServers test = new BusiestServers();

        // 1
        int[] arrival = {1, 2, 3, 4, 5};
        int[] load = {5, 2, 3, 3, 3};
        int k = 3;

        // 0
//        int[] arrival = {1, 2, 3, 4};
//        int[] load = {1, 2, 1, 2};
//        int k = 3;

        // [0, 1, 2]
//        int[] arrival = {1, 2, 3};
//        int[] load = {10,12,11};
//        int k = 3;

        // 1
//        int[] arrival = {1, 2, 3, 4, 8, 9, 10};
//        int[] load = {5, 2, 10, 3, 1, 2, 2};
//        int k = 3;

        // 0
//        int[] arrival = {1};
//        int[] load = {1};
//        int k = 1;

        List<Integer> list = test.busiestServers(k, arrival, load);
        System.out.println(list);
    }

    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) {
            map.put(i, 1);
        }
        int length = arrival.length;
        for (int i = 0; i < length; i++) {
            int st = arrival[i];
            while (!priorityQueue.isEmpty()) {
                long peek = priorityQueue.peek();
                if ((peek >> 32) <= st) {
                    priorityQueue.poll();
                    map.put((int) (peek), 1);
                } else {
                    break;
                }
            }
            int index = i % k;
            Integer value = map.ceilingKey(index);
            if (value == null) {
                value = map.ceilingKey(0);
            }
            if (value == null) {
                continue;
            }
            map.remove(value);
            arr[value]++;
            priorityQueue.add((((long) st + load[i]) << 32) + value);
        }
        int max = 0;
        for (int i = 0; i < k; i++) {
            max = Math.max(max, arr[i]);
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (arr[i] == max) {
                list.add(i);
            }
        }
        return list;
    }

}
